package com.qezhhnjy.leetcode.question.tree;

import com.qezhhnjy.leetcode.question.Generate;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author zhaoyangfu - 2020/12/6 20:22
 * 杨辉三角：https://leetcode-cn.com/problems/pascals-triangle/
 * 输入: 5
 * 输出:
 * [
 * [1],
 * [1,1],
 * [1,2,1],
 * [1,3,3,1],
 * [1,4,6,4,1]
 * ]
 */
public class PascalsTriangle implements Generate<Integer, List<List<Integer>>> {

    @Override
    public List<List<Integer>> generate(Integer numRows) {
        List<List<Integer>> result = new ArrayList<>();
        if (numRows < 1) {
            return result;
        }
        List<Integer> first = Collections.singletonList(1);
        result.add(first);
        if (numRows == 1) {
            return result;
        }
        for (int i = 2; i <= numRows; i++) {
            List<Integer> prev = result.get(i - 2);
            List<Integer> current = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                if (j == 0) current.add(prev.get(j));
                else if (j == i - 1) current.add(prev.get(j - 1));
                else current.add(prev.get(j - 1) + prev.get(j));
            }
            result.add(current);
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println(new PascalsTriangle().generate(5));
    }
}
